/**
 * NOTE: 线段树是一个平衡二叉树(最大深度和最小深度之差不超过 1, 不会退化成为一个链表, 存在 log 级别的查询操作 )
 * 我们底层使用数组来实现线段树, 那么我们需要将平衡二叉树变为满二叉树(一种特殊的完全二叉树)
 * 那么我们需要的空间将是 4n 个容量空间的数组空间,
 */

export type Merge<E> = (a: E, b: E) => E

/**
 * NOTE: 线段树: 将一段数据分成一块一块的区间, 来进行查询(比如: 按时间进行划分区间, 金额划分区间来进行查询)
 */
export class SegmentTree<E> {
  private data: E[] = []

  private merge!: Merge<E>

  private tree!: E[]
  constructor(arr: E[], merge: Merge<E>) {
    // NOTE: 开辟 4 个 length 的数组容量
    this.tree = new Array(arr.length * 4)
    this.merge = merge
    this.fillData(arr)
    this.buildSegmentTree(0, 0, arr.length - 1)
  }

  /**
   * query: [l...r]
   */
  public query(queryL: number, queryR: number): E {
    if (queryL < 0 || queryL >= this.data.length || queryR < 0 || queryR >= this.data.length) {
      throw new Error('invalid section')
    }
    return this.queryTree(0, 0, this.data.length - 1, queryL, queryR)
  }

  /**
   * update: 更新 index 位置的值, log(n)
   */
  public update(index: number, e: E) {
    if (index < 0 || index >= this.data.length) {
      throw new Error('invalid index')
    }
    this.data[index] = e
    this.updateTreeNode(0, 0, this.data.length - 1, index, e)
  }

  /**
   * print
   */
  public print() {
    this.tree.forEach((v) => {
      if (typeof v !== 'object') {
        console.log(v)
      }
    })
  }

  private updateTreeNode(treeIndex: number, l: number, r: number, index: number, e: E) {
    if (r === l) {
      this.tree[treeIndex] = e
      return
    }
    // tslint:disable-next-line:no-bitwise
    let mid = l + ((r - l) >> 1)

    let leftTreeIndex = this.getLeftChildIndex(treeIndex)
    let rightTreeIndex = this.getRightChildIndex(treeIndex)

    if (index >= mid + 1) {
      this.updateTreeNode(rightTreeIndex, mid + 1, r, index, e)
    } else {
      this.updateTreeNode(leftTreeIndex, l, mid, index, e)
    }

    this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex])
  }

  private queryTree(treeIndex: number, l: number, r: number, queryL: number, queryR: number): E {
    if (r === queryR && l === queryL) {
      return this.tree[treeIndex]
    }

    // tslint:disable-next-line:no-bitwise
    let mid = l + ((r - l) >> 1)
    let leftTreeIndex = this.getLeftChildIndex(treeIndex)
    let rightTreeIndex = this.getRightChildIndex(treeIndex)

    if (queryL >= mid + 1) { // 区间在右孩子中
      return this.queryTree(rightTreeIndex, mid + 1, r, queryL, queryR)

    } else if (queryR <= mid) { // 区间在左孩子中
      return this.queryTree(leftTreeIndex, l, mid, queryL, queryR)
    }

    // 区间在左右孩子中都存在
    let leftRet = this.queryTree(leftTreeIndex, l, mid, queryL, mid)
    let rightRet = this.queryTree(rightTreeIndex, mid + 1, r, mid + 1, queryR)

    return this.merge(leftRet, rightRet)
  }

  private fillData(arr: E[]) {
    for (let i = 0; i < arr.length; i++) {
      this.data[i] = arr[i]
    }
  }

  // NOTE: 创建以 treeIndex 为根节点的线段树, 这里先递归到底了, 再向上合并
  private buildSegmentTree(treeIndex: number, l: number, r: number) {
    if (l === r) {
      this.tree[treeIndex] = this.data[l]
      return
    }

    let leftTreeIndex = this.getLeftChildIndex(treeIndex)
    let rightTreeIndex = this.getRightChildIndex(treeIndex)

    // 区间范围
    // tslint:disable-next-line:no-bitwise
    let mid = l + ((r - l) >> 1)

    this.buildSegmentTree(leftTreeIndex, l, mid)
    this.buildSegmentTree(rightTreeIndex, mid + 1, r)

    this.tree[treeIndex] = this.merge(this.tree[leftTreeIndex], this.tree[rightTreeIndex])
  }

  private getLeftChildIndex(i: number): number {
    return i * 2 + 1
  }

  private getRightChildIndex(i: number): number {
    return i * 2 + 2
  }

}

// 扩展: 树状数组, RMQ: Range Minimum Query 区间相关的问题
